from typing import List


def count_islands(map: List[List[int]]) -> int:
    m = len(map)
    n = len(map[0])
    island_marker = map.copy()
    cnt = 0
    for i in range(m):
        for j in range(n):
            if island_marker[i][j]:
                dfs(island_marker, i, j, m, n)
                cnt += 1
    return cnt


def dfs(map, i, j, m, n):
    if i < 0 or j < 0 or i >= m or j >= n or map[i][j] == 0:
        return
    map[i][j] = 0
    dfs(map, i - 1, j, m, n)
    dfs(map, i + 1, j, m, n)
    dfs(map, i, j - 1, m, n)
    dfs(map, i, j + 1, m, n)


map1 = '''11110
11010
11000
00000'''

map2 = '''11000
11000
00100
00011
'''
print(count_islands([[int(y) for y in x] for x in map2.splitlines()]))
